#include "RMQ.cpp"

class Suggester{
    
public:
    
    explicit Suggester(std::vector<Node> &input){
        std::sort(input.begin(), input.end(), compWords);
        for (size_t i = 0; i < input.size(); ++i){
            input[i].index = i;
            data.push_back(input[i]);
        }
        mytree = RangeTree(input);
    }
    
    std::vector<Node> getSuggestions(std::string pref, size_t numberOfSuggestions){
        Node node;
        node.text = pref;
        node.freq = 0;
        node.index = 0;
        auto end = std::upper_bound(data.begin(), data.end(), node, ubComp);
        auto start = std::lower_bound(data.begin(), data.end(), node, lbComp);
        return getTop(start - data.begin(), end - data.begin() - 1, numberOfSuggestions);
    }
    
private:

    RangeTree mytree;
    std::vector<Node> data;
    
    struct heapNode{
        size_t leftBorder;
        size_t rightBorder;
        Node best;
    };
    
    static bool heapComp(heapNode a, heapNode b){
        return (a.best).freq < (b.best).freq;
    }
    
    static bool lbComp(Node a, Node b){
        if (a.text.size() < b.text.size())
            return a.text < b.text;
        std::string _a = std::string(a.text, 0, b.text.size());
        return _a < b.text;
    }
    
    static bool ubComp(Node a, Node b){
        if (b.text.size() < a.text.size())
            return a.text < b.text;
        std::string _b = std::string(b.text, 0, a.text.size());
        return a.text < _b;
    }

    static bool compWords (Node a, Node b){
        return a.text < b.text;
    }
    


    std::vector<Node> getTop(size_t start, size_t end, size_t numberOfSuggestions){
        if (numberOfSuggestions > end - start + 1)
            numberOfSuggestions = end - start + 1;
        std::vector<Node> result;
        std::vector<heapNode> bestSugHeap(1);
        bestSugHeap[0].leftBorder = start;
        bestSugHeap[0].rightBorder = end;
        bestSugHeap[0].best = mytree.rmq(start, end - 1);
        std::make_heap(bestSugHeap.begin(), bestSugHeap.end(), heapComp);
        
        for (size_t i = 0; i < numberOfSuggestions; ++i){
            heapNode theBest = bestSugHeap.front();
            std::pop_heap(bestSugHeap.begin(), bestSugHeap.end(), heapComp);
            bestSugHeap.pop_back();
            result.push_back(theBest.best);
            auto bestLeft = mytree.rmq(theBest.leftBorder + 1, theBest.best.index);
            auto bestRight = mytree.rmq(theBest.best.index + 2, theBest.rightBorder + 1);
            
            heapNode newBest;
            newBest.leftBorder = theBest.best.index + 1;
            newBest.rightBorder = theBest.rightBorder;
            newBest.best = bestRight;
            bestSugHeap.push_back(newBest);
            std::push_heap(bestSugHeap.begin(), bestSugHeap.end(), heapComp);
            newBest.leftBorder = theBest.leftBorder;
            newBest.rightBorder = theBest.best.index - 1;
            newBest.best = bestLeft;
            bestSugHeap.push_back(newBest);
            std::push_heap(bestSugHeap.begin(), bestSugHeap.end(), heapComp);
        }
        return result;
    }
};

std::vector<Node> getData(size_t n){
    std::vector<Node> input;
    Node in;
    int freq;
    std::string text;
    for (size_t i = 0; i < 20; ++i){
        std::cin >> text >> freq;
        in.text = text;
        in.freq = freq;
        input.push_back(in);
    }
    return input;
}

int main(){
    size_t n;
    std::cin >> n;
    auto input = getData(n);
    Suggester data(input);
    std::vector<Node> ans;
    std::string query = "";
    
    while(query != "EXIT"){
        std::cin >> query >> n;
        ans = data.getSuggestions(query, n);
        for (size_t i = 0; i < ans.size(); ++i){
            std::cout << ans[i].text << " " << ans[i].freq << "\n";
        }
    }
    
    return 0;
}
